#include<stdio.h>
#include<stdlib.h>
int v[100];
int e[20][20];
	int a;
	int b;
	int v1,v2;
	int c;
	int p[20];
	int d[20];
	int g;
	int mark[20];
void Init(){
   a=5;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			e[i][j]=12345;
		}
	}
   e[1][2]=22;
   e[0][1]=20;
   e[2][0]=33;
   e[4][2]=99;
   e[3][1]=25;
}
void Shortest_path(){
	p[0]=-1;
	for(int i=1;i<20;i++){
		p[i]=0;
		mark[i]=0;
		d[i]=e[0][i];
	} 
  int min;
  d[0]=0;
  int k;
  mark[0]=1;
  for(int i=0;i<a;i++){ 
min=12345;
for(int j=0;j<a;j++){
if(min>d[j]&&mark[j]==0){
min=d[j];
k=j;
			}
		}
		mark[k]=1;
		for(int g=0;g<a;g++){
			if((min+e[k][g]<d[g])&&mark[g]==0){
				d[g]=e[k][g]+min;
				p[g]=k;
			}
		}
	}}

void Check(){
	for(int i=0;i<a;i++){
		printf("%d %d %d\n",i,p[i],d[i]);
	}
}
int main(){
    Init();
	Shortest_path();
	Check();
}
